/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ruteador.control.geneticAlgorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Objects;
import java.util.Random;

/**
 *
 * @author jorgeorm
 */
public class CromosomaTSP {
    private ArrayList<Integer> recorrido;
    private int costoRecorrido;
    private int aptitud;
    private int edad;
    private int numeroPuntos;
    private int idPuntoInicial;
    
    public CromosomaTSP(int numeroPuntos, 
            ArrayList<Integer> recorrido, 
            int costo,
            int aptitud, 
            int edad){
        this.aptitud = aptitud;
        this.costoRecorrido = costo;
        this.edad = edad;
        this.recorrido = (ArrayList<Integer>) recorrido.clone();
        this.numeroPuntos = numeroPuntos;
    }
    
    public CromosomaTSP ( int numeroPuntos, ArrayList<Integer> recorrido){
        this.aptitud = -1;
        this.costoRecorrido = -1;
        this.edad = 0;
        this.numeroPuntos = numeroPuntos;
        this.recorrido = (ArrayList<Integer>) recorrido.clone();
    }
    
    public CromosomaTSP(int numeroPuntos, Random generador, int puntoInicial){
        this.numeroPuntos = numeroPuntos;
        this.idPuntoInicial = puntoInicial;
        recorrido = new ArrayList(numeroPuntos);
        /*Genero el cromosoma Básico
         */
        for(int i=0; i< numeroPuntos; i++){
            if(idPuntoInicial == i){
                continue;
            }
            else {
                recorrido.add(i);
            }
        }
        
        /*Determino el numero de mutaciones a realizar
         */
        int numeroPermutaciones;
        do{
            numeroPermutaciones = generador.nextInt(Integer.MAX_VALUE);
        }while(numeroPermutaciones <= numeroPuntos*2);
        /*Genero el cromosoma mutado
         */
        while (numeroPermutaciones>=0){
            int pos1 = generador.nextInt(numeroPuntos);
            int pos2 = generador.nextInt(numeroPuntos);
            
            int valorTmp = recorrido.get(pos1);
            
            recorrido.set(pos1, recorrido.get(pos2));
            recorrido.set(pos2, valorTmp);
                    
            numeroPermutaciones--;
        }
        
        recorrido.add(0, idPuntoInicial);
        recorrido.add(idPuntoInicial);
    }
    
    public ArrayList<Integer> getRecorrido(){
        return this.recorrido;
    }
    
    @Override 
    public CromosomaTSP clone(){
        CromosomaTSP cromo = new CromosomaTSP(numeroPuntos, 
                recorrido, 
                edad, 
                aptitud, 
                edad);
        return cromo;
    }
    
    @Override
    public String toString(){
        StringBuilder s_buff = new StringBuilder((2*numeroPuntos)+1);
        s_buff.append("[");
        for(int i = 0; i < numeroPuntos; i++){
            s_buff.append(recorrido.get(i));
            if(i<numeroPuntos-1){
                s_buff.append(',');
            }
        }
        s_buff.append("]");
        
        return s_buff.toString();
    }
    
    @Override
    public boolean equals(Object obj){
        CromosomaTSP objCromo;
        if(obj.getClass()!= this.getClass()) {
            return false;
        }
        else{
            objCromo=(CromosomaTSP)obj;
            if(this.numeroPuntos!=objCromo.getNumeroPuntos()){
                return false;
            }
            else if(this.aptitud!=objCromo.getAptitud()){
                return false;
            } else if (this.edad != objCromo.getEdad()){
                return false;
            } else if (this.costoRecorrido != objCromo.getCosto()){
                return false;
            }
            else{
                for(int i=0; i< numeroPuntos; i++){
                    if(recorrido.get(i) != objCromo.getRecorrido().get(i))  {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 3;
        hash = 53 * hash + Objects.hashCode(this.recorrido);
        return hash;
    }
    
    public CromosomaTSP mutar( int posRand1, int posRand2){
        CromosomaTSP cromoHijo;
        int posValue1, posValue2;
        
        
        ArrayList<Integer> recorridoHijo = (ArrayList<Integer>) recorrido.clone();
        
        int valorTmp = recorridoHijo.get(posRand1);
        
        recorridoHijo.set(posRand1, recorridoHijo.get(posRand2));
        recorridoHijo.set(posRand2, recorridoHijo.get(posRand1));
        
        cromoHijo=new CromosomaTSP(numeroPuntos, recorridoHijo);
        return cromoHijo;
    }
    
    
    public CromosomaTSP mutar(Random generador, double mutabilidad){
        /*Determino el numero de mutaciones a realizar
         */
        CromosomaTSP cromoResultado = this.clone();
        
        /*Determino el maximo de mutaciones permitidas
         */
        int cotaSup = (int) Math.round(mutabilidad*(double)numeroPuntos);
        
        int numeroPermutaciones = generador.nextInt(cotaSup);
        
        /*Genero el cromosoma mutado
         */
        while (numeroPermutaciones>=0){
            int pos1 ;
            int pos2 ;
            
            do{
                pos1 = generador.nextInt(numeroPuntos);
            }while(pos1 == 0);
            
            do{
                pos2 = generador.nextInt(numeroPuntos);
            }while(pos2 ==0);
            
            int valorTmp = recorrido.get(pos1);
            
            cromoResultado.getRecorrido().set(pos1, recorrido.get(pos2));
            cromoResultado.getRecorrido().set(pos2, valorTmp);
                    
            numeroPermutaciones--;
        }
        
        return cromoResultado;
    }
    
    public ArrayList<CromosomaTSP> reproducirCon(CromosomaTSP padre, int codonI, int codonF){
        ArrayList<CromosomaTSP> hijos = new ArrayList(2);
        ArrayList<Integer> recorridoHijo1, recorridoHijo2;
        
        recorridoHijo1 = new ArrayList(numeroPuntos+1);
        recorridoHijo2 = new ArrayList(numeroPuntos+1);
        
        /*Seteo las incongnitas
         */
        for(int i=0; i<numeroPuntos+1; i++){
            recorridoHijo1.set(i,-1);
            recorridoHijo2.set(i,-1);
        }
        
        /*Copio los segmentos que se conservan
         */
        for(int i=codonI; i<= codonF; i++){
            recorridoHijo1.set(i, padre.getRecorrido().get(i));
            recorridoHijo2.set(i, this.recorrido.get(i));
        }
        
        /*Lleno las incongnitas
         */
        int idxHijo1=0;
        int idxHijo2=0;
        /*No toca el ultimo punto para el copiado
         */
        for(int i=codonF+1; i<numeroPuntos; i++){
            /*Me ubico en la primera variable de arrayHijo1
             */
            while(recorridoHijo1.get(idxHijo1) != -1){
                if(idxHijo1 < numeroPuntos-1) {
                    idxHijo1++;
                }
                if(idxHijo1 == numeroPuntos-1) {
                    break;
                }
            }
            /*Me ubico en la primera variable de arrayHijo2
             */
            while(recorridoHijo2.get(idxHijo2) != -1){
                if(idxHijo2 < numeroPuntos-1) {
                    idxHijo2++;
                }
                if(idxHijo2 == numeroPuntos-1) {
                    break;
                }
            }
            
            /*Pregunto si el alelo ya está en el cromosoma1 y si no esta lo meto
             */
            if(!estaEnArrayList(recorridoHijo1, recorrido.get(i))){
                recorridoHijo1.set(idxHijo1, recorrido.get(i));
            }
            
            /*Pregunto si el alelo ya está en el cromosoma2 y si no esta lo meto
             */
            if(!estaEnArrayList(recorridoHijo2, padre.getRecorrido().get(i))){
                recorridoHijo2.set(idxHijo2, padre.getRecorrido().get(i));
            }
        }
        
        /*
         * Lleno las incognitas del tablero utilizando alelos de los padres 
         * de inicio respentando el punto inicial a posFin
         */
        for(int i=1; i<=numeroPuntos;i++)
        {
            //Me ubico en la primera variable de arrayHijo1
            while(recorridoHijo1.get(idxHijo1)!=-1){
                if(idxHijo1<numeroPuntos-1){
                    idxHijo1++;
                }
                if(idxHijo1==numeroPuntos-1){
                    break;
                }
            }
            //Me ubico en la primera variable de arrayHijo2
            while(recorridoHijo2.get(idxHijo2)!=-1){
                if(idxHijo2<numeroPuntos-1){
                    idxHijo2++;
                }
                if(idxHijo2==numeroPuntos-1){
                    break;
                }
            }
            if(!estaEnArrayList(recorridoHijo1,recorrido.get(i))){
                recorridoHijo1.set(idxHijo1, recorrido.get(i));
//                System.out.println("Puse de Madre: "+tablero[i]);

            }
            if(!estaEnArrayList(recorridoHijo2,padre.getRecorrido().get(i))){
                recorridoHijo2.set(idxHijo2, padre.getRecorrido().get(i));
//                System.out.println("Puse de Padre: "+cromosomaPadre.getTablero()[i]);
            }
        }
        
        /*
         * Verificar si el punto inicial ya está antes de hacer esto
         * para descartar malos funcionamientos
         */
        
        recorridoHijo1.add(0, idPuntoInicial);
        recorridoHijo2.add(0, idPuntoInicial);
        recorridoHijo1.add(idPuntoInicial);
        recorridoHijo2.add(idPuntoInicial);
        
        hijos.add(new CromosomaTSP(numeroPuntos, recorridoHijo1));
        hijos.add(new CromosomaTSP(numeroPuntos, recorridoHijo2));
        
        return hijos;
    }
    
    
    
    private boolean estaEnArrayList(ArrayList<Integer> array, int dato){
        boolean esta = false;
        
        /*Búsqueda binaria
         */
        int tam= numeroPuntos;
        int inicio, fin;
        inicio =0;
        fin = numeroPuntos -1;
        
        /*Ordeno el arreglo para hacer búsqueda binária
         */
        
        ArrayList<Integer> arregloTemporal = (ArrayList<Integer>) array.clone();
        Collections.sort(arregloTemporal);
        
        
        /*Hago búsqueda binaria
         */
        int mitad;
        
        BUSQBIN: while(!esta && tam > 1){
            mitad = (int) Math.round(((double)inicio+fin)/2.0);
            if(dato == arregloTemporal.get(mitad)){
                esta = true;
                continue BUSQBIN;
            }else{
                if(dato < arregloTemporal.get(mitad)){
                    fin = mitad;
                }else if(dato > arregloTemporal.get(mitad)){
                    inicio = mitad;
                }
            }
        }
        
        if(tam == 1) {
            esta = (dato == arregloTemporal.get(inicio)) ||
                (dato == arregloTemporal.get(fin));
        }
        
        return esta;
    }

    public int getNumeroPuntos() {
        return numeroPuntos;
    }

    public int getAptitud() {
        return aptitud;
    }

    public int getEdad() {
        return edad;
    }

    public int getCosto() {
        return costoRecorrido;
    }
}
